package book;

public class HeapSortSolution {
    
    void swap(int[] a, int i, int j) {
        int temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }

    // 构建堆
    int[] heap(int[] nums) {
        int[] h = new int[nums.length + 1];
        for (int i = 1; i <= nums.length; i++) {
            h[i] = nums[i - 1];
            for (int k = i; 
                k > 1 && h[k] > h[k / 2]; 
                    swap(h, k, k / 2), k /= 2);
        }
        return h;
    }

    // 堆排序
    int[] heapSort(int[] h) {
        System.out.println("堆排序开始：");
        int n = h.length - 1;
        int step = 1;
        for (int k = n; k >= 2; k--) {
            int i = 1;
            swap(h, i, k);
            while (i < k) {
                int j = i * 2;
                if (j + 1 < k && h[j + 1] > h[j]) 
                    j = j + 1;
                if (j < k && h[j] > h[i]) {
                    swap(h, i, j);
                    i = j;
                }
                else break;
            }
            System.out.println("第" + (step++) + "步:" + display(h, 1));
        }
        return h;
    }

    public static void main(String[] args) {
        HeapSortSolution sln = new HeapSortSolution();
        int[] nums = { 24, 61, 7, 92, 4, 6, 44 };
        System.out.println("原数组：\n" + display(nums, 0) + "\n");

        // 构建堆
        int[] h = sln.heap(nums);
        System.out.println("构建出来的堆为：\n" + display(h, 1) + "\n");

        // 堆排序
        h = sln.heapSort(h);
        System.out.println("\n最终堆排序结果为：\n" + display(h, 1) + "\n");
    }

    static String display(int[] arr, int start) {
        StringBuffer buf = new StringBuffer();
        for (int i = start; i < arr.length; i++)
            buf.append("\t").append(arr[i]);
        return buf.toString();
    }
}
